<?php
require $root . "/ArrayStruct/ArrayStruct.php";

class MaxHeap
{
    private $array = null;

    /**
     * 构造函数 初始化堆的容量
     * MinHeap constructor.
     * @param int $capacity
     */
    public function __construct(int $capacity = 10)
    {
        $this->array = new ArrayStruct($capacity);
    }

    /**
     * 返回堆的元素个数
     * @return int
     */
    public function getSize(): int
    {
        return $this->array->getSize();
    }

    /**
     * 判断堆是否为空
     * @return bool
     */
    public function isEmpty(): bool
    {
        return $this->array->isEmpty();
    }

    /**
     * 计算某个索引 $i 节点父亲节点索引值 $i父+1 = ($i+1)/2 取整，即 $i父 = ($i-1)/2 取整
     * @param $i
     * @return int
     */
    private function parent($i): int
    {
        if ($i == 0) {
            echo "索引 0 是没有父亲节点的";
            exit;
        }
        return (int)(($i - 1) / 2);
    }

    /**
     * 计算某个索引 $i 节点左儿子节点索引值 $i左+1 = ($i+1)*2 取整，即 $i左 = 2*$i+1
     * @param $i
     * @return int
     */
    private function leftSon($i): int
    {
        return $i * 2 + 1;
    }

    /**
     * 计算某个索引 $i 节点右儿子节点索引值 $i右+1 = ($i+1)*2+1 取整，即 $i左 = 2*$i+2
     * @param $i
     * @return int
     */
    private function rightSon($i): int
    {
        return $i * 2 + 2;
    }

    /**
     * 向堆中添加元素
     * @param $e
     */
    public function add($e): void
    {
        $this->array->addLast($e);
        $this->siftUp($this->array->getSize() - 1);
    }

    public function increment($i): void
    {
        $e = $this->array->get($i);
        $this->array->set($i, ['key' => $e['key'], 'value' => $e['value'] + 1]);
    }

    /**
     * 元素上浮
     * @param $i
     */
    private function siftUp($i)
    {
        while ($i > 0 && $this->array->get($this->parent($i))['value'] < $this->array->get($i)['value']) {
            $this->swsp($i, $this->parent($i));
            $i = $this->parent($i);
        }
    }

    /**
     * 元素下沉
     * @param $i
     */
    private function siftDown($i)
    {
        while ($i < $this->array->getSize() / 2) {
            $leftSon  = $this->array->get($this->leftSon($i));
            $rightSon = $this->array->get($this->rightSon($i));
            if (!empty($leftSon) && empty($rightSon) && $this->array->get($i)["value"] < $leftSon["value"]) {
                $this->swsp($i, $this->leftSon($i));
                $i = $this->leftSon($i);
            } elseif (empty($leftSon) && !empty($rightSon) && $this->array->get($i)["value"] < $rightSon["value"]) {
                $this->swsp($i, $this->rightSon($i));
                $i = $this->rightSon($i);
            } elseif (!empty($leftSon) && !empty($rightSon) && ($this->array->get($i)["value"] < $rightSon["value"] || $this->array->get($i)["value"] < $leftSon["value"])) {
                if ($rightSon["value"] < $leftSon["value"]) {
                    $this->swsp($i, $this->leftSon($i));
                    $i = $this->leftSon($i);
                } else {
                    $this->swsp($i, $this->rightSon($i));
                    $i = $this->rightSon($i);
                }
            } else {
                break;
            }
        }
    }

    /**
     * 查看堆中最大的元素
     * @return mixed
     */
    public function findMax()
    {
        if ($this->array->isEmpty()) {
            echo "堆是空的";
            exit;
        }
        return $this->array->get(0);
    }

    public function getMax()
    {
        $max = $this->findMax();
        $this->array->set(0, $this->array->removeLast());
        //删除操作
        if ($this->array->getSize() > 1) {
            $this->siftDown(0);
        }

        return $max;
    }

    public function replaceMax($e)
    {
        $min = $this->findMax();
        $this->array->set(0, $e);
        $this->siftDown(0);
        return $min;
    }

    /**
     * 交换堆中元素值
     */
    public function swsp($i, $parentI)
    {
        $parentE = $this->array->get($parentI);
        $e       = $this->array->get($i);
        $this->array->set($i, $parentE);
        $this->array->set($parentI, $e);
    }

    public function toString()
    {
        return $this->array->toString();
    }
}